package com.fr.lintcode;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

public class Q866 {
	//回溯

    /**
     * @param A: a list of integer
     * @param B: an integer
     * @return: return a list of integer
     */
	int lowPrice = Integer.MAX_VALUE;
	List<Integer> rs = new ArrayList<>();
    public List<Integer> cheapestJump(int[] A, int B) {
        // write your code here
    	int totalPrice = 0;
    	List<Integer> tmp = new ArrayList<>();
    	bianli(0, totalPrice, tmp, A, B);
    	return rs;
    }
	private void bianli(int i, int totalPrice, List<Integer> tmp, int[] a, int b) {
		if(i >= a.length) {
			return;
		}
		if(a[i] == -1) {
			return;
		}
		totalPrice += a[i];
		tmp.add(i + 1);
		if (i == a.length - 1) {
			saveResult(totalPrice, tmp);
			totalPrice -= a[i];
			tmp.remove(tmp.size() - 1);
			return;
		}
		
		for(int j = 1; j <= b && i+j < a.length; j ++) {
			bianli(i + j, totalPrice, tmp, a, b);
		}
		totalPrice -= a[i];
		tmp.remove(tmp.size() - 1);
		
	}
	private void saveResult(int totalPrice, List<Integer> tmp2) {
		if(rs.size() == 0) {
			rs = new ArrayList<>(tmp2);
			lowPrice = totalPrice;
		}else {
			if (lowPrice > totalPrice) {
				rs =  new ArrayList<>(tmp2);;
				lowPrice = totalPrice;
			}else if(lowPrice == totalPrice){
				int length = Math.min(rs.size(), tmp2.size());
				for(int i = 0; i < length; i++) {
					if(tmp2.get(i) == rs.get(i)) {
						continue;
					}else if (tmp2.get(i) <= rs.get(i)) {
						rs =  new ArrayList<>(tmp2);
						break;
					}else {
						break;
					}
				}
			}
		}
	}
	
	@Test
	public void testCheapestJump() {
		int A[] = {84,31,75,96,48,91,1,4,17,69,97,71,75,92,20,4,66,39,66,71,30,21,45,72,91,70,22,14,47,76,77,92,95,55,47,39,14,22,54,9,12,58,5,1,45,63,40,-1,28,17,52,31,80,41,51,24,97,50,55,50,35,52,97,-1,36,73,9,72,94,36,39,40,23,78,84};
		int B = 49;
		cheapestJump(A, B);
		System.out.println(rs);
		
	}


}
